`
https://leetcode.cn/problems/target-sum/
`

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var findTargetSumWays = function (nums, target) {
  if (nums.length === 0) return 0
  const memo = new Map()

  // 定义：利用 nums[i..] 这些元素，能够组成和为 remain 的方法数量
  function backtrack(i, remain) {
    // base case
    if (i === nums.length) {
      if (remain === 0) return 1;
      return 0;
    }

    // 把它俩转成字符串才能作为哈希表的键
    const key = `${i},${remain}`;

    // 避免重复计算
    if (memo.has(key)) {
      return memo.get(key);
    }

    // 还是穷举
    const result = backtrack(i + 1, remain - nums[i]) + backtrack(i + 1, remain + nums[i]);

    // 记入备忘录
    memo.set(key, result);
    return result;
  }

  return backtrack(0, target)
};